package cn.edu.njust.alg.leetcode;

/**
 * 创建时间：2015年6月15日 上午11:47:37 项目名称：AlgorithmExercise
 * 
 * @author Zhou Xiumin
 * @version 1.0
 * @since JDK 1.7.0_21 文件名称：Leetcode_0_t.java 类说明：
 */
public class Leetcode_200_Number_of_Islands {

	public static void dfs(char[][] grid, int i, int j) {
		if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length
				|| grid[i][j] != '1') {
			return;
		}
		grid[i][j] = '0';
		int[][] dir = { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };
		for (int k = 0; k < dir.length; k++) {
			dfs(grid, i + dir[k][0], j + dir[k][1]);
		}
	}

	public static int numIslands(char[][] grid) {
		int count = 0;
		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[i].length; j++) {
				if (grid[i][j] == '1') {
					count++;
					dfs(grid, i, j);
				}
			}
		}
		return count;
	}

	public static void main(String[] args) {
		char[][] grid = { { '1', '1', '0', '0', '0' },
				{ '1', '1', '0', '0', '0' }, { '0', '0', '1', '0', '0' },
				{ '0', '0', '0', '1', '1' } };
		System.out.println(numIslands(grid));
	}

}
